8.14 Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that n is prime if and only if n divides (2n - 2). a. Give an example that satisfies the condition using an odd prime. b. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime (proving the if condition) c. Give an example of an odd n that is not prime and that does not satisfy the condition. You can do this with nonprime numbers up to a very large value. This misled the Chinese mathematicians into thinking that if the condition is true then n is prime. d. Unfortunately, the ancient Chinese never tried n = 341, which is nonprime (341 = 11 * 31), yet 341 divides 2341 - 2 without remainder. Demonstrate that 2341 K 2 (mod 341) (disproving the only if condition). Hint: It is not necessary to calculate 2341; play around with the congruences instead. | |
| View Solution | |
| << Back | Next >> |